#include <stdio.h>
#include <stdlib.h>

// https://www.zhihu.com/column/developer1024


#define MAX_SIZE 100 // 定义最大容量

typedef int KeyType;
typedef int InfoType;

typedef struct sortdatatype
{
    KeyType key;
    InfoType otherinfo;
} RecType, *ArrList;

typedef RecType SeqList[MAX_SIZE];

/** 模板
 * 思想: 
 * 
 * 时间复杂度为 O(N^2)
 * 空间复杂度为 O(1)
 *
 * 最坏情况时间复杂度为 O(N^2)
 * 最佳情况的时间复杂度为 O(N)
*/

// 打印数组
void printArray(int arr[], int len)
{
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

void printSeqList(SeqList R, int len)
{
    for (int i = 0; i < len; i++)
        printf("%d ", R[i].key);
    printf("\n");
}

void init(SeqList R, int arr[], int len)
{
    for (int i = 0; i < len; i++)
    {
        R[i].key = arr[i];
    }
    
    printf(">>>The before sorting array: ");
    printSeqList(R, len);
}